#include <iostream>
#include <vector>

using namespace std;

class Solution01 {
    vector<int> tmp;
public:
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        return MergeCount(nums, 0, nums.size() - 1);
    }

    int MergeCount(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int leftcount = MergeCount(nums, left, mid);
        int rightcount = MergeCount(nums, mid + 1, right);

        // 左右两边已经有序，计算翻转对
        int midcount = 0;
        int cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right) {
            long long key = nums[cur2];
            key += nums[cur2];
            if ((long long)nums[cur1] > key) {
                midcount += mid - cur1 + 1;
                cur2++;
            } else {
                cur1++;
            }
        }

        int i = 0;
        cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right) 
            if (nums[cur1] <= nums[cur2])
                tmp[i++] = nums[cur1++];
            else
                tmp[i++] = nums[cur2++];
        
        while (cur1 <= mid) tmp[i++] = nums[cur1++];

        while (cur2 <= right) tmp[i++] = nums[cur2++];

        for (int i = left; i <= right; i++) nums[i] = tmp[i - left];
        
        return midcount + leftcount + rightcount;
    }
};

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution02 {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* tail = head;
        ListNode *cur1 = l1, *cur2 = l2;
        int next = 0;
        while (cur1 || cur2) {
            int x = 0;
            x += next;
            if (cur1)
                x += cur1->val, cur1 = cur1->next;
            if (cur2)
                x += cur2->val, cur2 = cur2->next;
            next = x / 10;
            x %= 10;

            ListNode* newnode = new ListNode(x);
            tail->next = newnode;
            tail = newnode;
        }
        if (next) {
            ListNode* newnode = new ListNode(next);
            tail->next = newnode;
            tail = newnode;
        }
        return head->next;
    }
};

class Solution03 {
public:
    ListNode* swapPairs(ListNode* head) {
        // 使用快慢指针
        if (head == nullptr) return nullptr;
        ListNode* newhead = new ListNode(0);
        newhead->next = head;
        ListNode* slow = head, *fast = head->next, *tail = newhead;
        while (slow && fast) {
            ListNode* slownext = slow->next->next;
            ListNode* fastnext = nullptr;
            if (slownext) fastnext = slownext->next;
            
            // 交换 fast 和 slow
            fast->next = slow;
            slow->next = slownext;
            tail->next = fast;
            tail = slow;

            // 迭代更新 slow fast
            slow = slownext;
            fast = fastnext;
        }
        return newhead->next;
    }
};

class Solution04 {
public:
    void reorderList(ListNode* head) {
        // 第一个链表顺序
        // 第二个链表逆序
        // if (head == nullptr || head->next == nullptr) return;
        // ListNode* slow = head, *fast = head->next;

        // ListNode* listfirst = new ListNode();
        // ListNode* listsecond = new ListNode();

        // ListNode* tailfirst = listfirst;
        
        // // 第一个链表使用尾插，第二个链表使用头插
        // while (slow && fast) {
        //     ListNode* slownext = fast->next;
        //     ListNode* fastnext = nullptr;
        //     if (slownext) fastnext = slownext->next;

        //     slow->next = nullptr;
        //     tailfirst->next = slow;
        //     tailfirst = slow;

        //     ListNode* next = listsecond->next;
        //     fast->next = next;
        //     listsecond->next = fast;

        //     slow = slownext;
        //     fast = fastnext;
        // }
        // // 有可能 slow 和 fast 其中有一个没有加上去
        // if (fast) {
        //     ListNode* next = listsecond->next;
        //     fast->next = next;
        //     listsecond->next = fast;
        // }

        // if (slow) {
        //     slow->next = nullptr;
        //     tailfirst->next = slow;
        //     tailfirst = slow;
        // }

        if (head == nullptr || head->next == nullptr) return;
        ListNode* slow = head, *fast = head->next;
        ListNode* mid = nullptr;
        while (slow && fast) {
            slow = slow->next;
            ListNode* next = fast->next;
            if (next == nullptr) break;
            fast = next->next;
        }
        mid = slow;

        ListNode* listfirst = new ListNode();
        ListNode* listsecond = new ListNode();
        listsecond->next = nullptr;
        slow = head, fast = mid->next;
        mid->next = nullptr;
        listfirst->next = slow;
        ListNode* tailfirst = listfirst;

        while (fast) {
            ListNode* next1 = listsecond->next, *nextfast = fast->next;
            fast->next = next1;
            listsecond->next = fast;            
            fast = nextfast;
        }

        Print(listfirst->next);
        Print(listsecond->next);
        // 将两个链表给链接起来
        // 先连接slow
        // 需要一个尾节点
        slow = listfirst->next, fast = listsecond->next;
        head = slow;
        ListNode* tail = head;
        int cnt = 0;
        slow = slow->next;
        while (slow && fast) {
            if (cnt % 2 == 0) {
                tail->next = fast;
                tail = fast;
                fast = fast->next;
            } else {
                tail->next = slow;
                tail = slow;
                slow = slow->next;
            }
            cnt++;
        }

        if (slow) {
            tail->next = slow;
            // slow->next = nullptr;
        }
        if (fast) {
            tail->next = fast;
            // fast->next = nullptr;
        }
        
        Print(head);
    }

    void Print(ListNode* head) {
        ListNode* cur = head;
        while (cur->next) {
            std::cout << cur->val << "->";
            cur = cur->next;
        }
        std::cout << cur->val << std::endl;
    }
};

int main() {
    ListNode* head = new ListNode(1);
    ListNode* n1 = new ListNode(2);
    ListNode* n2 = new ListNode(3);
    ListNode* n3 = new ListNode(4);
    ListNode* n4 = new ListNode(5);
    ListNode* n5 = new ListNode(6);
    head->next = n1, n1->next = n2, n2->next = n3, n3->next = nullptr, n4->next = nullptr, n5->next = nullptr;
    Solution04 s;
    s.reorderList(head);
    return 0;
}